package leetcode;

import java.util.*;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-26 10:47
 **/
public class LeetCode5965 {

    /*public long[] getDistances(int[] arr) {
        //key存储值,value存储相同值的下标
        Map<Integer, List<Integer>> map = new HashMap<>();
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            map.computeIfAbsent(arr[i], (k) -> new ArrayList<>()).add(i);
        }

        long[] ans = new long[n];
        for (int i = 0; i < n; i++) {
            List<Integer> list = map.get(arr[i]);
            for (int num : list) {
                if (num != i) {
                    ans[i] += Math.abs(num - i);
                }
            }
        }

        return ans;
    }*/

    public long[] getDistances(int[] arr) {
        //key存储的是值,value集合存储的是相同值对应的下标集合
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            map.computeIfAbsent(arr[i], t -> new ArrayList<>()).add(i);
        }
        long[] result = new long[arr.length];
        //遍历map的value
        for (List<Integer> list : map.values()) {
            //先计算出当前集合第一个元素所对应的间隔和,后续集合中的其它元素都可根据第一个间隔和推算出来
            for (int i : list) {
                result[list.get(0)] += i - list.get(0);
            }
            //遍历其它的相同元素,并根据第集合中第一个元素对应的间隔和推算出来
            for (int i = 1; i < list.size(); i++) {
                result[list.get(i)] = result[list.get(i - 1)] + (2L * i - list.size()) * (list.get(i) - list.get(i - 1));
            }
        }
        return result;
    }

    public static void main(String[] args) {
        LeetCode5965 code = new LeetCode5965();
        System.out.println(Arrays.toString(code.getDistances(new int[]{1, 1, 1, 1, 1, 1, 1, 1})));


    }
}
